package algorithm.sort;

import java.util.Arrays;

/**
 * 归并排序:将数组逐步拆分,直到拆到每个数组只剩一个元素,然后开始向上归并
 * @author jiaqi.han
 * @date 2021年3月24日
 */
public class MergeSort extends CommonSort implements Sortable {

	public void sort(int[] targetArr) {
		MergeSort mergeSort = new MergeSort();
		int[] result = mergeSort.mergeSort(targetArr);
		displaySortedArray(-1, result);
	}

	public int[] mergeSort(int[] targetArr) {
		if (targetArr.length < 2) {
			return targetArr;
		}
		MergeSort mergeSort = new MergeSort();
		int mid = targetArr.length / 2;
		int[] left = Arrays.copyOfRange(targetArr, 0, mid);
		int[] right = Arrays.copyOfRange(targetArr, mid, targetArr.length);
		int[] result = mergeSort.merge(mergeSort(left), mergeSort(right));
		return result;
	}

	/**
	 * 传入两个待归并数组,返回一个归并好的数组,即排好序的数组
	 * @author jiaqi.han
	 * @date 2021年3月24日
	 */
	public int[] merge(int[] left, int[] right) {
		int[] result = new int[left.length + right.length];
		for (int index = 0, i = 0, j = 0; index < result.length; index++) {
			if (i >= left.length) {
				result[index] = right[j++];
			} else if (j >= right.length) {
				result[index] = left[i++];
			} else if (left[i] > right[j]) {
				result[index] = right[j++];
			} else {
				result[index] = left[i++];
			}
		}
		return result;
	}

}
